МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Я.П. Романчук ДИСКРЕТНА МАТЕМАТИКА Конспект лекцій Розглянутий на засіданні кафедри АСУ як навчальний посібник для студентів базового напрямку 050101 «Комп’ютерні науки» денної та заочної форм навчання (протокол № 1-10/11 від 31 серпня 2010 р.) Львів − 2010 УДК 519.1+519.6 Я.П. Романчук. Дискретна математика: Конспект лекцій для студентів напряму комп’ютерні науки спеціальності Інформаційні управляючі системи та технології. – Львів: НУЛП, 2010. – 210 с. У конспекті викладено теорію множин і відношень; алгебру логіки і алгебру логіки висловлень і предикатів, теорію графів, моделі алгоритмів і програм, формальні граматики й мови, основи теорії кодування та шифрування. Кожен розділ складається з основних визначень, властивостей, операцій і теорем; має значну кількість розв’язаних і ілюстрованих прикладів з об’єктами дискретної природи; містить вправи для аудиторної та самостійної роботи студентів. Конспект лекцій може бути корисним для студентів інших спеціальностей, які бажають вивчати методи дискретної математики для використання їх у природничих і гуманітарних науках із залученням інформаційних технологій. Рецензент: І.М. Дронюк, кандидат фізико-математичних наук, доцент кафедри АСУ. Відповідальна за випуск: З.Я. Шпак, кандидат технічних наук, доцент кафедри АСУ. Лекція 4 6. ҐРАФИ Ґрафічне представлення розв’язків різних прикладних задач є загальновідомим. До ґрафів у широкому сенсі можуть бути віднесені малюнки, креслення, ґрафіки, діаграми, блок-схеми тощо. З їх використанням наочно ілюструються залежності між процесами та явищами, логічні, структурні, причинно-наслідкові та інші взаємозв’язки. Однак, теорія ґрафів має свою власну проблематику. У дискретній математиці ґраф є найважливішим математичним поняттям. На основі теорії ґрафів будуються моделі різноманітних задач, таких як маршрутизації, розподілу ресурсів, дискретної оптимізації, сіткового планування та керування, аналізу й проектування організаційних структур, аналізу процесу їх функціонування та багато іншого. 6.1. Основні означення. Означення 6.1. Ґрафом
називається сукупність двох множин:
− точок і
− ліній, між якими вказане відношення інцидентності (належності), причому, кожен елемент
інцидентний тільки двом елементам
. Елементи множини
називаються вершинами, а елементи множини
 ребрами ґрафу. Вершини і ребра ґрафу називаються його елементами, тому найчастіше пишуть
і
. Означення 6.2. Якщо ребро
з’єднує вершини
, тоді вони є для нього кінцевими точками і називаються суміжними вершинами. Два ребра називаються суміжними, якщо вони інцидентні до спільної вершини. Зауважимо, що при показанні ґрафу не всі деталі малюнка мають значення. Так, наприклад, несуттєвими є довжина і кривизна ребер, взаємне розташування вершин на площині. Принциповим є тільки відношення інцидентності. Приклад 6.1. Моделі, що показані на рис. 6.1 а, б, в, теорія ґрафів трактує як однакові. / / / а б в Рис. 6.1. У деяких задачах теорії ґрафів інцидентні ребру вершини нерівноправні, а розглядаються в певному порядку. Тоді кожному ребру можна вказати, наприклад, напрямок − від першої інцидентної вершини до другої. Означення 6.3. Напрямлені ребра називають орієнтованими ребрами або дугами, перша по черзі вершина називається початком дуги, а друга – її кінцем. Ґраф, який містить напрямлені ребра, називається орієнтованим ґрафом або орґрафом (рис. 6.2, а), а ґраф, що не містить напрямлених ребер – неорієнтованим або н-ґрафом (рис. 6.2, б). / / (а) (б) Рис. 6.2. Означення 6.4. Ребро, що з’єднує деяку вершину саму із собою, називається петлею (рис. 6.3,а). Означення 6.5. Ребра, інцидентні до однієї і тієї ж вершини, називаються кратними (рис. 6.3,б). Ґраф, який має кратні ребра, називається мультиґрафом, а ґраф, що містить кратні ребра і петлі – псевдоґрафом. Означення 6.6. Ґраф називається скінченним, якщо ...